1749. 任意子数组和的绝对值的最大值

Similar Question

Solution Tips

方案一: 贪心 + 分情况讨论

其实就是把 53. 最大子数组和 做两遍

var maxAbsoluteSum = function(nums) {
    let positiveMax = 0, negativeMin = 0;
    let positiveSum = 0, negativeSum = 0;
    for (let num of nums) {
        positiveSum += num
        positiveMax = Math.max(positiveMax, positiveSum)
        positiveSum = Math.max(0, positiveSum)
        negativeSum += num
        negativeMin = Math.min(negativeMin, negativeSum)
        negativeSum = Math.min(0, negativeSum)
    }
    return Math.max(positiveMax, -negativeMin)
};

方案二: 前缀和

var maxAbsoluteSum = function (nums) {
    let s = 0, mx = 0, mn = 0;
    for (const x of nums) {
        s += x;
        mx = Math.max(mx, s);
        mn = Math.min(mn, s);
    }
    return mx - mn;
};